#include<stdlib.h>
#include<iostream>
#include<stdio.h>
#include<time.h>
#include"assert.h"

using namespace std;

struct Fraction
{
public:
    int nom;
    int denom;
};

int gcd(int min,int max)
{
    if(min==0) return 1;
    while(min!=0)
    {
        int temp=min;
        min=max%min;
        max=temp;
    }

    return max;
}

Fraction force(int arr[],int length,int m)
{
    Fraction *temp=new Fraction();
    Fraction &max=(*temp);
    max.denom=1;
    max.nom=0;

    ///initialize a array to contain sums of input array's part
    //int sum[length][length];  //this line can occur stack overflow!

    int **sum=new int*[length];
    for(int i=0;i<length;i++)
        sum[i]=new int[length];

    for(int i=0; i<length; i++)
        for(int j=0; j<length; j++)
            sum[i][j]=0;

    for(int i=0; i<length; i++)
        sum[i][i]=arr[i];

    ///sum[3][5]=sum[3][4]+sum[4][5]
    for(int pos=0; pos<length; pos++)
    {
        for(int i=0; i<length; i++)
        {
            if((i+pos)<length)
            {
                if(i+pos>i) ///if pos is 0,just ingore, the value has been set for this sum values.
                {
                    sum[i][i+pos]=sum[i][(2*i+pos)/2]+sum[(2*i+pos)/2+1][i+pos];
                }

                if(pos>=(m-1) && sum[i][i+pos]*max.denom>max.nom*(pos+1))//update max if need.
                {
                    max.denom=pos+1;
                    max.nom=sum[i][i+pos];
                }
            }
        }
    }

    for(int i=0;i<length;i++)
    {
        delete[] sum[i];
    }
    delete[] sum;

    return max;
}

Fraction dp(int arr[],int length,int m)
{
    Fraction max;
    max.denom=0,max.nom=0;

    Fraction current;
    current.denom=0,current.nom=0;

    Fraction test;
    test.denom=0,test.nom=0;

    int pos=m-1;
    int i=0,j=-1;

    bool changedMark=false;

    while(j<length)
    {
        if((j-i)>pos)
        {
            test.denom=0,test.nom=0;
            for(int k=0; k<(j-i-pos); k++)
            {
                test.nom+=arr[i+k];
                test.denom+=1;
                if(test.nom*current.denom<=current.nom*test.denom)
                {
                    for(int j=0; j<k+1; j++)
                    {
                        current.nom-=arr[i+j];
                        current.denom-=1;
                    }
                    i+=(k+1);

                    changedMark=true;
                    break;
                }
            }
            if(changedMark==true)
            {
                changedMark=false;
                continue;
            }

        }


        if(j-i>=pos)
        {
            if(max.nom*current.denom<=current.nom*max.denom)
            {
                max.denom=current.denom;
                max.nom=current.nom;
            }
        }

        j++;
        if(j<length)
        {
            current.nom+=arr[j];
            current.denom+=1;
        }
    }
    return max;
}

const int MAXArrayLength=1000;
const int IntRange=1000;
int ArrToTest[MAXArrayLength];
int LengthOfArrayToTest=0;
int Span=0;

void RandomizeArr()
{
    //srand(time(NULL));

    LengthOfArrayToTest=rand()%(MAXArrayLength+1);
    if(LengthOfArrayToTest==0) LengthOfArrayToTest=5;
    Span=rand()%LengthOfArrayToTest;

    if(Span==0) Span++;

    for(int i=0; i<LengthOfArrayToTest; i++)
    {
        ArrToTest[i]=rand()%IntRange;
    }
}

int main()
{
    int arr[]= {100,100,5,100,100};
    Fraction result=force(arr,5,3);
    Fraction result2=dp(arr,5,3);
    cout<<result.nom<<"/"<<result.denom<<endl;
    cout<<result2.nom<<"/"<<result2.denom<<endl;

    int g=0;
    for(int i=0; i<1000; i++)
    {
        RandomizeArr();
        Fraction r1=force(ArrToTest,LengthOfArrayToTest,Span);
        if(r1.nom<r1.denom)
            g=gcd(r1.nom,r1.denom);
        else
            g=gcd(r1.denom,r1.nom);

        r1.nom/=g;
        r1.denom/=g;

        Fraction r2=dp(ArrToTest,LengthOfArrayToTest,Span);
        if(r1.nom<r2.denom)
            g=gcd(r2.nom,r2.denom);
        else
            g=gcd(r2.denom,r2.nom);

        r2.nom/=g;
        r2.denom/=g;
        /*//test infomation output
        for(int i=0;i<LengthOfArrayToTest;i++)
        cout<<ArrToTest[i]<<" ";
        cout<<endl;
        cout<<"Length is:"<<LengthOfArrayToTest<<" Span is:"<<Span<<endl;
        //*/
        cout<<r1.nom<<"/"<<r2.denom<<"=="<<r2.nom<<"/"<<r2.denom<<endl;

        assert(r1.nom==r2.nom && r1.denom==r2.denom);
    }
    return 0;
}
